package easy;

public class Solution_744 {

    public char nextGreatestLetter(char[] letters, char target) {
        if (letters[letters.length-1] <= target) {
            return letters[0];
        }
        int begin = 0, end = letters.length - 1;
        for (;begin<end;) {
            if (begin + 1 == end) {
                if (letters[begin] > target) {
                    return letters[begin];
                } else if (letters[end]>target) {
                    return letters[end];
                }
                return letters[end+1];
            }
            int middle = (begin + end) / 2;
            if (letters[middle] <= target) {
                begin = middle;
            } else {
                end = middle;
            }
        }
        return ' ';
    }

    public static void main(String[] args) {
        Solution_744 model = new Solution_744();
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'a'));
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'c'));
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'd'));
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'g'));
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'j'));
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'k'));
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'c', 'j'}, 'c'));
        System.out.println(model.nextGreatestLetter(new char[]{'c', 'c'}, 'c'));
    }
}
